package com.example.algorithm.dp;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

//完全背包
public class Week4 {
    //    N件物品和最多重量为W的背包。
    //    第i件物品重量weight[i]，价值value[i]
    //    每件物品无限个（可以放入背包多次），求将物品装入背包价值总和最大
    //先遍历物品，再遍历背包
    private static void testCompletePack() {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagWeight = 4;
        int[] dp = new int[bagWeight + 1];
        for (int i = 0; i < weight.length; i++) { // 遍历物品
            //            从小到大去遍历
            for (int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        for (int maxValue : dp) {
            System.out.println(maxValue + "   ");
        }
    }

    //    零钱兑换II
    //    不同面额硬币和总金额。凑成总金额的硬币组合数。每种硬币有无限个。
    //    求组合数就是外层遍历物品，内层遍历背包。
    //    求排列数就是外层遍历背包，内层循环遍历物品。
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        //初始化dp数组，金额为0时只有一种情况，什么都不装
        dp[0] = 1;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }

    //    组合总和
    //    nums = [1, 2, 3]
    //    target = 4
    //    组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 0; i <= target; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (i >= nums[j]) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }

    //    爬楼梯（进阶版）
    //每次可以爬至多m (1 <= m < n)个台阶。有多少种方法
    public static void main1(String[] args) {
        int m = 2, n = 3;
        // 求排列问题，先遍历背包再遍历物品
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int j = 1; j <= n; j++) {
            for (int i = 1; i <= m; i++) {
                if (j - i >= 0) dp[j] += dp[j - i];
            }
        }
        System.out.println(dp[n]);
    }

    //    零钱兑换
    //  不同面额的硬币coins无限，总金额amount。
    //    凑成总金额所需的最少的硬币个数。没有任何一种组合返回 -1
    public int coinChange(int[] coins, int amount) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[amount + 1];
        //初始化dp数组为最大值
        Arrays.fill(dp, max);
        //当金额为0时需要的硬币数目为0
        dp[0] = 0;
        for (int coin : coins) {
            //正序遍历：完全背包每个硬币可以选择多次
            for (int j = coin; j <= amount; j++) {
                //只有dp[j-coins[i]]不是初始最大值时，该位才有选择的必要
                if (dp[j - coin] != max) {
                    //选择硬币数目最小的情况
                    dp[j] = Math.min(dp[j], dp[j - coin] + 1);
                }
            }
        }
        return dp[amount] == max ? -1 : dp[amount];
    }

    //    完全平方数
    //   正整数 n，找到若干完全平方数（比如 1, 4, 9, 16, ...）和等于 n。个数最少。
    //先遍历物品, 再遍历背包
    public int numSquares(int n) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[n + 1];
        //初始化
        for (int j = 0; j <= n; j++) {
            dp[j] = max;
        }
        dp[0] = 0;
        for (int i = 1; i * i <= n; i++) {
            for (int j = i * i; j <= n; j++) {
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }
        return dp[n];
    }

    //  单词拆分
    //  非空字符串s和包含非空单词列表wordDict，s 是否可以被空格拆分为一或多个在wordDict出现的单词
    //  本题们求是排列数，为什么呢。
    //            "applepenapple", wordDict = ["apple", "pen"]
    //            物品的组合一定是 "apple" + "pen" + "apple"其他不可以
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>(wordDict);
        boolean[] valid = new boolean[s.length() + 1];
        valid[0] = true;

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i && !valid[i]; j++) {
                if (set.contains(s.substring(j, i)) && valid[j]) {
                    valid[i] = true;
                }
            }
        }

        return valid[s.length()];
    }

    //    多重背包
    //    有N种物品容量V背包。
    //    第i种物品最多有Mi件可用，每件耗费Ci ，价值Wi 。
    //    物品装入背包耗费的空间和不超过容量，且价值总和最大。
    //    多重背包和01背包非常像的，把Mi件摊开，就是01背包
    public static void main2(String [] args) {
        int bagWeight = 10, n = 3;
        int[] weight = {1,3,4};
        int[] value = {15,20,30};
        int[] nums = {4,30,2};
        int[] dp = new int[bagWeight + 1];
        //先遍历物品再遍历背包，作为01背包处理
        for (int i = 0; i < n; i++) {
            for (int j = bagWeight; j >= weight[i]; j--) {
                //遍历每种物品个数
                for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) {
                    dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);
                }
            }
        }
        System.out.println(dp[bagWeight]);
    }
}

/*背包递推公式
    能否装满背包（或最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
        分割等和子集(opens new window)
        最后一块石头的重量 II(opens new window)
   装满背包有几种方法：dp[j] += dp[j - nums[i]]
        目标和(opens new window)
        零钱兑换 II(opens new window)
        组合总和Ⅳ(opens new window)
        爬楼梯进阶版（完全背包）(opens new window)
   背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        一和零(opens new window)
   装满背包所有物品最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
        零钱兑换(opens new window)
        完全平方数(opens new window)
*/
